package com.mlh.binarytree;

import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/8/23 11:55
 * @DESCRIPTION
 */
//给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
public class 二叉搜索树中第K小的元素 {
    //方法一：利用迭代进行中序遍历
    public int method1(TreeNode root, int k) {
        LinkedList<TreeNode>stack=new LinkedList<>();
        int count=0;
        while(root!=null){
            stack.addLast(root);
            root=root.left;
        }
        while (!stack.isEmpty()){
            TreeNode node = stack.pollLast();
            count++;
            if(count==k){
                return node.val;
            }
            node=node.right;
            while(node!=null){
                stack.addLast(node);
                node=node.left;
            }
        }
        return -1;
    }

    public int practice(TreeNode root, int k) {
        LinkedList<TreeNode>stack=new LinkedList<>();
        while(root!=null){
            stack.addLast(root);
            root=root.left;
        }
        while(!stack.isEmpty()){
            TreeNode temp=stack.pollLast();
            if(k==1){
                return temp.val;
            }
            k--;
            temp=temp.right;
            while(temp!=null){
                stack.addLast(temp);
                temp=temp.left;
            }
        }
        return 0;
    }
}
